package com.lanluo.service.sort;

/**
 * 归并排序
 * 图解(https://www.cnblogs.com/chengxiao/p/6194356.html)
 *
 * @author
 * @date 2018-08-28-15:56
 */
public class Merge extends Example{

    private static Comparable[] aux;    //归并所需的辅助数组

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    /**
     * 自顶向下的归并排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi) {
        if(hi <= lo) return;
        int mid = lo + (hi - lo)/2;
        sort(a, lo, mid);       //将左半边排序
        sort(a, mid+1, hi); //将右半边排序
        merge(a, lo, mid, hi);  //归并结果
    }

    /**
     * 将a[lo..mid]和a[mid+1..hi]归并
     * @param a
     * @param lo
     * @param mid
     * @param hi
     */
    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;

        //将a[lo..hi]复制到aux[lo..hi]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid)                  a[k] = aux[j++]; //左边元素耗尽，取右半边元素
            else if(j > hi)               a[k] = aux[i++]; //右边元素耗尽，取左半边元素
            else if(less(aux[j], aux[i])) a[k] = aux[j++]; //如果右边元素小于左边元素, 取右边元素
            else                          a[k] = aux[i++]; //如果左边元素大于等于右边元素, 取左边元素
        }
    }

    public static void main(String[] args) {
        String[] a = {"D", "B", "A", "C", "E"};
        sort(a);
        System.out.println(isSorted(a));
        show(a);
    }

}